// 思路：按每个元素的位数分别进行排序，按照低位优先法

function radixSort(arr) {
    // 1. 桶的大小为所有元素的最大位数
    let size = String(Math.max(...arr)).length
    // 从低位到高位依次遍历每一位，以各个数位值为索引，对数组进行按位排序
    for (let i = 0; i < size; i++) {
        // 使用一个长度为10的桶来存放各个位上的元素
        let buckets = new Array(10).fill(0).map(_ => [])
        // 遍历数组元素，根据元素对应位上的值，将其存入对应的桶中
        for (let j = 0; j < arr.length; j++) {
            let index = Math.floor((arr[j] / Math.pow(10, i))) % 10
            buckets[index].push(arr[j])            
        }
        // 清空原始数组
        arr = []
        // 从桶中依次取出对应元素，并重新加入到原始数组
        for (let j = 0; j < buckets.length; j++) {
            arr.push(...buckets[j])            
        }
    }
    return arr
}

// 时间复杂度O((n+m) * k) , n为待排序数组的长度，m为桶的数量，k为最大数字位数
// 空间复杂度为O(n+m)
// 稳定排序

let arr = [2, 7, 26, 25, 19, 17, 1, 90, 3, 36]
console.log(radixSort(arr));